package com.maltys.dp.sequence;

import java.util.Arrays;

public class DistinctSubsequences {
    public static void main(String[] args) {
        DistinctSubsequences subsequences = new DistinctSubsequences();
        int distinct = subsequences.numDistinct("babgbag", "bag");
        System.out.println(distinct);
    }

    /**
     * 计算在 s 的⼦序列中 t 出现的个数
     * 1. 相等的时候，dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
     * dp[i][j] = dp[i-1][j-1]
     * 2. 不相等的时候 删除这个字符，删除之后，就是dp[i][j-1]
     * dp[i][j] = dp[i-1][j]
     *
     * @param s 子序列
     * @param t 目标字符串
     * @return 出现个数
     */
    public int numDistinct(String s, String t) {
        int[][] dp = new int[t.length() + 1][s.length() + 1];
        for (int i = 0; i <= s.length(); i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i <= t.length(); i++) {
            for (int j = 1; j <= s.length(); j++) {
                if (t.charAt(i - 1) == s.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                dp[i][j] += dp[i][j - 1];
            }
        }
        return dp[t.length()][s.length()];
    }
}
